package com.binarysearch;

import java.util.ArrayList;
import java.util.List;

public class Solution658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int i = 0;
        int j = arr.length - 1;
        while (i < j) {
            int mid = i + j + 1 >> 1;
            if (arr[mid] <= x) i = mid;
            else j = mid - 1;
        }
        i = i + 1 < arr.length && Math.abs(arr[i + 1] - x) < Math.abs(arr[i] - x) ? i + 1 : i;
        int l = i - 1;
        int r = i + 1;
        while (r - l - 1 < k) {
            if (l >= 0 && r < arr.length) {
                if (Math.abs(arr[l] - x) > Math.abs(arr[r] - x)) r++;
                else l--;
            } else if (l >= 0) l--;
            else r++;
        }
        List<Integer> res = new ArrayList<>();
        for (int m = l + 1; m < r; m++) {
            res.add(arr[m]);
        }
        return res;
    }
}
